package leetcode_day._2022._202208._2131;

import general_class.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 662. 二叉树最大宽度
 * 算法：深度优先搜索
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/27 22:01
 */
public class _27 {

    Map<Integer, Integer> map;
    int ans;

    public int widthOfBinaryTree(TreeNode root) {
        map = new HashMap<>();
        dfs(root, 1, 0);
        return ans;
    }

    void dfs(TreeNode node, int u, int depth) {
        if (node == null) return;
        if (!map.containsKey(depth)) map.put(depth, u);
        ans = Math.max(ans, u - map.get(depth) + 1);
        u = u - map.get(depth) + 1;
        dfs(node.left, u << 1, depth + 1);
        dfs(node.right, u << 1 | 1, depth + 1);
    }

}
